package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 199. 二叉树的右视图
 * https://leetcode.cn/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入: [1,2,3,null,5,null,4]
 * 输出: [1,3,4]
 * 示例 2:
 *
 * 输入: [1,null,3]
 * 输出: [1,3]
 * 示例 3:
 *
 * 输入: []
 * 输出: []
 *
 *
 * 提示:
 *
 * 二叉树的节点个数的范围是 [0,100]
 * -100 <= Node.val <= 100
 */
public class Problem199 {
    public static void main(String[] args) {
        Integer[] ints=new Integer[]{};
        TreeNode instanceNew = TreeNode.getInstanceNew(ints);

        Problem199 problem199 = new Problem199();
        List<Integer> integers = problem199.rightSideView(instanceNew);
        System.out.println(integers);

    }

    /**
     * 思路:
     * 维护一个ArrayList和当前访问节点的level
     * 进行任何一种遍历, 无脑将节点顺序覆盖ArrayList对应的节点上即可
     *
     * 注: 题目中没有说明是何种二叉树, 因而不可仅遍历某一个分支, 必须全部都遍历才能保证没有空缺
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        preOrder(root,0);
        return resultList;
    }

    private List<Integer> resultList=new ArrayList<>();

    public void preOrder(TreeNode treeNode,int level){
        if(treeNode==null){
            return;
        }
        if(level==resultList.size()){
            resultList.add(treeNode.val);
        }else{
            resultList.set(level,treeNode.val);
        }

        preOrder(treeNode.left,level+1);
        preOrder(treeNode.right, level+1);

    }
}
